МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Я.П. Романчук ДИСКРЕТНА МАТЕМАТИКА Конспект лекцій Розглянутий на засіданні кафедри АСУ як навчальний посібник для студентів базового напрямку 050101 «Комп’ютерні науки» денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.) Львів − 2010 УДК 519.1+519.6 Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с. У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування. Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів. Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій. Рецензент: І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ. Відповідальна за випуск: З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ. Лекція 5 7. КОМБІНАТОРИКА У цьому розділі розв’язуються деякі задачі, пов’язані з розглядом різних комбінацій з елементів кінцевих множин М. Наприклад, якщо взяти 10 різних цифр 0, 1, 2, ... , 9 і утворювати з них комбінації, то будемо одержувати різні числа, наприклад 345, 534, 1036, 5472, 45, 54 і т.п. Видно, що деякі з таких комбінацій відрізняються тільки порядком цифр (наприклад 345 і 534), інші − вхідними в них цифрами (наприклад 1036 і 5472), треті − розрізняються і порядком і числом цифр (наприклад 345 і 54). Отримані комбінації задовольняють різним умовам. Залежно від правил їх утворення можна виділити три типи комбінацій: перестановки, розміщення, сполучення. Розглянемо їх окремо. 7.1. Перестановки. Означення 7.1. Комбінації з n елементів, які відрізняються одна від іншої тільки порядком елементів, називаються перестановками. Перестановки позначаються символом Рn, де n — число елементів, які входять у кожну перестановку. Приклад 7.1. Нехай множина М містить три букви А, В, С. Складемо всі можливі комбінації із цих букв: АВС, АСВ, ВСА, CAB, CBA, ВАС (усього 6 комбінацій). Видно, що вони відрізняються одна від іншої тільки порядком розташування букв. Дійсно, на перше місце в комбінації (перестановці) можна поставити три букви. На друге місце вже можна поставити тільки дві букви із трьох (одна посіла перше місце), а на третьому виявиться тільки одна (та, що залишилася). Виходить, 3 · 2 · 1 = 6 = P3 , але 1 · 2 · 3 = 3! Прийшли до відомого у математиці поняття факторіалу. Означення 7.2. Добуток всіх натуральних чисел від 1 до n включно називають n-факторіалом і пишуть: n!= 1 · 2 · 3 · ... · (n - 1) · n. Вважають, що 0! = 1 і
. Основна властивість факторіалу: (n + 1)! = (n +1) · n!. Отже, число перестановок обчислюємо за формулою: Рn = n! (7.1) 7.2. Розміщення. Означення 7.3. Комбінації з n елементів по m елементів, які відрізняються одна від другої або самими елементами або порядком елементів, називаються розміщеннями. Розміщення позначаються символом
, де n − число всіх наявних елементів, m − число елементів у кожній комбінації. Число розміщень можна обчислити за формулою:
, де 0 ≤ m ≤ n; m, n
N. (7.2) Вважають, що
. Приклад 7.2. Нехай множина M містить чотири букви А, В, С, D. Склавши всі комбінації тільки із двох букв, одержимо: АВ, AC, AD, ВА, ВР, BD, СА, СВ, CD, DA, DB, DC. Видно, що всі отримані комбінації (їх 12) відрізняються або буквами, або їхнім порядком (комбінації ВА і АВ вважаються різними). За формулою (7.2)
, що збігається з результатом наведеного прикладу. Тут кожен рядок відповідає однієї із всіх наявних...